package code2101_2200.code60_70;

/**
 * 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
 *
 * 给你一个可能存在 重复 元素值的数组 numbers ，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。
 * 请返回旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转，该数组的最小值为1。 
 *
 * 输入：[3,4,5,1,2]
 * 输出：1
 *
 * 输入：[2,2,2,0,1]
 * 输出：0
 */
public class _2168minArray {

    /**
     * 思考 ： 本质上就是找数组中的最小元素，常规便利的话为O(n),O(1)。但估计想达到要求，时间最起码为O(logn)
     * 加上旋转和排序 重新思考： 只需要找到数组中第一个元素在原数组中的位置即可，最终结果返回nums.length - index;
     * 找位置的话 第一下想到的就是二分法。但原数组包含了重复数字，直接二分不能判断是否是这个重复数字。
     *
     * 在思考：当前这个元素无法判断是否为重复元素，则找到下一个元素即可，即使他是重复元素，也是最左边元素，很方便找到。
     * 但这种方法好像不行，因为输入的是旋转后的数组，旋转前的数组不知道。得另辟蹊径！
     *
     * 直接二分查找好像也可以
     *
     * // 自己试了一下，此二分查找的最关键点在于，当值相等时候如何处理。题解中说明如下。
     * 我们并不能确定 究竟在最小值的左侧还是右侧，因此我们不能莽撞地忽略某一部分的元素。
     * 我们唯一可以知道的是，由于它们的值相同，所以无论是不是最小值，都有一个它的「替代品」，因此我们可以忽略二分查找区间的右端点。
     *
     * 思考 ： 题解中min是按照最大的来看，此处是按最小的来看，故是将右边++；
     *
     * 执行用时：     * 0 ms     * , 在所有 Java 提交中击败了     * 100.00%     * 的用户
     * 内存消耗：     * 38.2 MB     * , 在所有 Java 提交中击败了     * 56.84%     * 的用户
     *
     * @param numbers
     * @return
     */
    public static int minArray(int[] numbers) {
        if(numbers.length==1)return numbers[0];
        int min = numbers[0];
        int left = 0;
        int right = numbers.length-1;
        int mid;
        while (left<right){
            mid = left+(right-left+1)/2;
            if(numbers[mid]>min){
                left = mid;
            }else if(numbers[mid]<min){
                min = numbers[mid];
                right = mid;
            }else {
                min = numbers[++left]>min?min:numbers[left];
            }
        }
        return min;
    }

    public static void main(String[] args) {
        int[] nums = {2,2,2,0,1};
        System.out.println(minArray(nums));
    }

}
